
//汉诺塔
class Solution {
public:
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        dfs(a,b,c,a.size());
    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n)
    {
        if(n==1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a,c,b,n-1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b,a,c,n-1);

    }
};


//合并链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr)
            return list2;
        if(list2 ==nullptr)
            return list1;
        if(list1->val > list2->val)
        {
            list2->next =mergeTwoLists(list1,list2->next);
            return list2;
        }
        else
        {
            list1->next =mergeTwoLists(list1->next,list2);
            return list1;
        }
    }


};

//反转链表
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
            return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next=nullptr;
        return newhead;
    }
};

//两两交换位置
//迭代的方式
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr)
            return nullptr;
        
        ListNode* prev = head;
        ListNode* Next=head->next;
        if(!Next)
        {
            return head;
        }
        ListNode* newhead = Next;

        //当两个均不为空的时候，开始交换
        ListNode* tmp=nullptr;
        ListNode* father=nullptr;
        while(prev && Next )
        {
            tmp=Next->next; //Next的后续节点
            Next->next = prev;
            prev->next = tmp;
            if(father!=nullptr)
            {
                father->next=Next;
            }
            //改变完成之后，修改指向
            if(tmp!=nullptr)
            {
                father = prev;
                prev=tmp;
                Next=prev->next;
                
            }
            else
            {
                break;
            }        
        }
        return newhead;
    }
};
//递归方式
class Solution {
public:

    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr ||  head->next == nullptr )
            return head;
        ListNode* newnode = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = newnode;
        return ret;

    }
};


//快速幂
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        long long t =abs(n); //这里如果2^2-31作为abs的话，就会超出最大范围
        double tmp= myPow(x,t/2);
        if(n<0)
        {
            tmp = 1/tmp;
            return (t%2)==0?tmp*tmp:tmp*tmp*(1/x);
        }
        else
        {
            return (t%2)==0?tmp*tmp:tmp*tmp*x;
        }
        
    }
};


//二叉树的递归
// 2331. 计算布尔二叉树的值
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root->left ==nullptr)
            return root->val;
        return root->val==2?evaluateTree(root->left) | evaluateTree(root->right):evaluateTree(root->left) & evaluateTree(root->right);


    }
};
//129. 求根节点到叶节点数字之和
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }

    int dfs(TreeNode* root,int psum)
    {
        psum = psum*10+root->val;
        if(root->left == nullptr && root->right ==nullptr)
            return psum;

        int ret =0;
        if(root->left) ret+=dfs(root->left,psum);
        if(root->right) ret+=dfs(root->right,psum);
        return ret;
    }
};

//814. 二叉树剪枝
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(root==nullptr)
            return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(root->right == nullptr && root->left == nullptr && root->val==0)
        {
            delete root;
            root=nullptr;
        }
        return root;
    }
};

//验证二叉搜索树
class Solution {
public:
    long prev=LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr)
            return true;
        bool left = isValidBST(root->left);
        if(left==false) return false;
        bool cur =false;
        if(root->val > prev)
            cur=true;
        if(cur==false) return false;
        prev = root->val;
        bool right = isValidBST(root->right);
        return right&& left&&cur;
        
    }
};
